The field of the invention relates to digital arithmetic means, and more particularly to digital arithmetic means employing parallel digital coding for obtaining the square of a number of value.
In the digital multiplication of two numbers, a variety of schemes has evolved in the digital processor art. A survey of some of these is treated in the text "Digital Signal Processing" by Peled and Liu, published by John Wiley and Sons, Inc., New York (1976). For example, a 2's complement type of serial multiplier is illustrated in FIG. 4.3 in Section 4.2, Binary Arithmetic, while FIG. 4.4 illustrates a 4-bit array multiplier as a means of speeding up the serial multiplier process, but which yet requires a substantial number of operations and corresponding processing time. Page 182 in such Section 4.2 discusses a "two bits at a time" or "N-bits at a time" as an alternate method for speeding up multiplication. FIG. 4.4 of Section 4.1 of the above-noted reference "Digital Signal Processing" illustrates a 4-bit array multiplier by which the partial products of all the bits are generated and added up. However, all of these methods involve substantial delays or processing time and associated gating hardware.
The current availability of miniaturized read-only memories, or ROM's, has allowed a change in the approach to digital multiplier mechanizations, whereby the multiplication of two numbers may be reduced to use of a set of look-up tables in memory: the product of any two values may be quickly determined by addressing the memory (ROM) by means of such set of values and "looking up" or reading out the answer stored at such address. Thus, the number of products obtainable is limited by the word size of the two values-to-be-multiplied and the size or capacity of the memory. In other words, the capacity of the memory imposes limits on the number of products which may be stored and addressed as a function of the address-word size.
In commercial practice, the size of chips (upon which memory cells may be mounted) tends to be standardized, while the density of memory cells that may be placed on a chip is limited.
A method of reducing the memory size required for a given size ROM type multiplier has been described in the article "A Specially Designed ROM for Multiplication", by C. van Holten, published in Microelectronics, Vol. 9, No. 1 at pp 25-26, published by Mackintosh Publications, Ltd., 1978). Such reference discloses the utilization of auxiliary logic (a comparator and zero detector) in conjunction with the ROM, and employing the concepts that the product of A.times.B is the same as that of B.times.A and for either A or B equal to zero, the product AB is zero. Thus, the zero detector commands a zero product output without referencing or addressing the ROM, while the comparator routes the larger of A and B to a major side of an abbreviated memory matrix, the redundant portion of the matrix being omitted from the memory. While the economy achieved is better than 50%, such result is not significant in terms of the mechanization demands made by current highly sophisticated, high-density digital-data processors.